nLab symmetric group

Idea

The permutations of a set $X$ form a group, $S_X$, under composition. This is especially clear if one thinks of the permutation as a bijection on $X$, where the multiplication / composition is just composition of functions. This group is called the symmetric group of $X$ and often denoted $S_X$, $\Sigma_X$, $Sym(X)$ or similar.

The subgroups of symmetric groups are the permutation groups.

When $X$ is the finite set $(n) = \{1,\dots,n\}$, then its symmetric group is a finite group of cardinality $n!$ = “$n$ factorial”, and one typically writes $S_n$ or $\Sigma_n$.

(We will make frequent use of the entry permutation for some key notation and concepts.)

In general, an element of $S_n$ can be represented by a two row array

$$\sigma= \left(\array{1&2&\ldots &n\\\sigma(1)&\sigma(2)&\ldots&\sigma(n)}\right).$$

It can also be given in cycle notation. We repeat the example from the entry on permutations. This is from $S_6$:

Let $\sigma$ be the permutation on $(6)$ defined by

$$\sigma = (\array{1 \mapsto 1 & 2\mapsto 4 & 3 \mapsto 5 & 4 \mapsto 6 & 5 \mapsto 3 & 6 \mapsto 2})= \left(\array{1&2&3&4&5&6\\1&4&5&6&3&2}\right)$$

The domain of the permutation is partitioned into three $\langle\sigma\rangle$-orbits

$$(6) = \{1\} \cup \{2,4,6\} \cup \{3,5\}$$

corresponding to the three cycles

$$1 \underset{\sigma}{\to} 1 \qquad 2 \underset{\sigma}{\to} 4 \underset{\sigma}{\to} 6 \underset{\sigma}{\to} 2 \qquad 3 \underset{\sigma}{\to} 5 \underset{\sigma}{\to} 3$$

We express this more compactly by writing $\sigma$ as the composition $\sigma = (1)(2\,4\,6)(3\,5)$, or $\sigma = (2\,4\,6)(3\,5)$ leaving implicit the action of the identity (1).

We can also write $\sigma$ as a product of transpositions

$$(2\,4)(2\,6)(3\,5)$$

Examples

The symmetric group $S_3$

$S_3$ is the group of permutations of $(3)=\{1,2,3\}$.

One simple way to represent an element of $S_3$ is by listing the $(3)$ on the top row of an array with a second row denoting the image of each element under the permutation. For instance, the element $sigma= (1\mapsto 2, 2\mapsto 1, 3\mapsto 3)$ can be written more compactly as

$$\sigma= \left(\array{1&2&3\\2&1&3}\right).$$

We can also use, even more compactly, ‘cycle notation’, as explained in more detail at permutation, in which successive images under the permutation, $\sigma$, are listed until you get back to where you started. Elements of (3), or more generally of (n), are usually not listed as cycles of length 1, exept that (1) may be used to indicate the identity element. For the above permutation, this gives

$$\sigma = (1\,2)$$

the transposition exchanging the elements 1 and 2 and leaving 3 ‘unmoved’. Whilst the 3-cycle, $(1\,2\,3)$, shifts every element to the right one position and then maps 3 to 1.

Example

(Cayley graph of Sym(3)) The following shows the Cayley graph of the symmetric groups on 3 elements, $Sym(3)$, with edges corresponding to any transposition (not necessarily adjacent), hence whose graph distance is the Cayley distance:

The symmetric group $S_4$

The symmetric group on 4 elements is isomorphic to the full tetrahedral group as well as to the orientation-preserving octahedral group.

Properties

Cycle decomposition

As an element of the symmetric group $S_X$, every permutation $\sigma : X \to X$ generates a cyclic subgroup $\langle \sigma \rangle$, and hence inherits a group action on $X$. The orbits of this action partition the set $X$ into a disjoint union of cycles, called the cyclic decomposition of the permutation $\sigma$.

For example, let $\sigma$ be the permutation on $(6)$ defined by

$$\sigma = (\array{1 \mapsto 1 & 2 \mapsto 4 & 3 \mapsto 5 & 4 \mapsto 6 & 5 \mapsto 3 & 6 \mapsto 2})$$

The domain of the permutation is partitioned into three $\langle\sigma\rangle$-orbits

$$(6) = \{1\} \cup \{2,4,6\} \cup \{3,5\}$$

corresponding to the three cycles

$$1 \underset{\sigma}{\to} 1 \qquad 2 \underset{\sigma}{\to} 4 \underset{\sigma}{\to} 6 \underset{\sigma}{\to} 2 \qquad 3 \underset{\sigma}{\to} 5 \underset{\sigma}{\to} 3$$

We can express this more compactly by writing $\sigma$ in “cycle notation”, as the composition $\sigma = (1)(2\,4\,6)(3\,5)$, or $\sigma = (2\,4\,6)(3\,5)$ leaving implicit the action of the identity (1).

Even in the simple example of $S_3$ one can see some patterns.

• $(12)$ clearly has order 2, whilst $(123)$ has square $(132)$, which is also the inverse of $(123)$, and has order 3.

• $(123) = (12)(13)$, so transpositions generate the whole group.

This gives a listing of the elements of $S_3$ as

$$\{ 1, (12),(13),(23),(123),(132)\}.$$

• $S_3$ has a presentation

$$\langle a,b | a^3, b^2,(a b)^2 \rangle.$$

where $a$ corresponds to the 3-cycle, $(123)$, whilst $b$ corresponds to any transposition. It also has a presentation in which the generators correspond to the transpositions:

$$\langle \sigma_1,\sigma_2 | \sigma_1^2,\sigma_2^2, (\sigma_1\sigma_2)^3\rangle$$

It is easy to see that these relations imply that

$$\sigma_1\sigma_2\sigma_1= \sigma_2\sigma_1\sigma_2$$

which relates this symmetric group to the braid group, Br 3, and to the trefoil group. It is clear that there is an epimorphism $S_3\to Br_3$ obtained by making the two braid generators become the transpositions.

Conjugacy classes

Proposition

(conjugacy classes of the symmetric group labeled by partitions by cycle lengths)

Let $n \in \mathbb{N}$ and $\Sigma(n)$ the symmetric group on $n$ elements. Then the conjugacy classes of elements of $\Sigma(n)$, hence of permutations of $n$ elements, correspond to the cycle structures: two elements are conjugate to each other precisely if they have the same number $\# cycles \in \mathbb{N}$ of distinct cycles of the same lengths $(l_1 \geq l_2 \geq \cdots \geq l_{\#cycles})$, hence equivalently if they define the same underlying partition

$$l_1 + l_2 + \cdots + l_{\# cycles} \;=\; n$$

of $n$.

(e.g. Sagan 01, p. 3 (18 of 254))

Example

For the symmetric group on three elements there are three such classes:

(1 2 3) ~ (1 3 2)

(1 2)(3) ~ (1 3)(2) ~ (1)(2 3)

(1)(2)(3)

$\,$

$\,$

$\,$

$\,$

$\,$

$\,$

---

Representation theory

See at representation theory of the symmetric group.

Relation to the field with one element

One may regard the symmetric group $S_n$ as the general linear group in dimension $n$ on the field with one element $GL(n,\mathbb{F}_1)$.

See there.

Classifying space and universal Thom space

The classifying space $B \Sigma(n)$ of the symmetric group on $n$ elements may be presented by $Emb(\{1,\cdots, n\}, \mathbb{R}^\infty)/\Sigma(n)$, the Fadell's configuration space on $n$ unordered points in $\mathbb{R}^\infty$.

(e.g. Bödigheimer 87, Example 10)

Write $\tau_n$ for the rank $n$ vector bundle over this which exhibits the canonical action of $\Sigma(n)$ on $\mathbb{R}^n$, by permutation of coordinates.

The Thom space $B \Sigma(n)^{\tau_n}$ of this bundle appears as the cofficients of the spectral symmetric algebra of the “absolute spectral superpoint” $Sym_{\mathbb{S}} \Sigma \mathbb{S}$ (see Rezk 10, slide 4).

See also (Hopkins-Mahowald-Sadofsky 94, around def. 2.8)

Whitehead tower and relation to supersymmetry

The symmetric groups and alternating groups are the first stages in a restriction of the Whitehead tower of the orthogonal group to “finite discrete ∞-groups” in the sense of homotopy type with finite homotopy groups. The homotopy fibers of the stages of the “finite Whitehead tower” are the stable homotopy groups of spheres (Epa-Ganter 16). (See also at super algebra – Abstract idea and at Platonic 2-group.)

$$\array{ && && \vdots \\ && && \downarrow \\ && && \mathbf{B}Fivebrane(n) \\ && \downarrow && \downarrow \\ \mathbf{B}^2 \pi_3 \mathbb{S} &\stackrel{}{\longrightarrow} & \mathbf{B}\mathcal{A}_n &\hookrightarrow& \mathbf{B} String(n) \\ && \downarrow && \downarrow \\ \mathbf{B} \pi_2 \mathbb{S} &\longrightarrow & \mathbf{B} \tilde A_n &\hookrightarrow& \mathbf{B} Spin(n) \\ && \downarrow && \downarrow \\ \pi_1 \mathbb{S} &\longrightarrow& \mathbf{B} A_n &\hookrightarrow& \mathbf{B} SO(n) \\ && \downarrow && \downarrow \\ && \mathbf{B} S_n &\hookrightarrow& \mathbf{B} O(n) }$$

• on the right: the delooped smooth ∞-group Whitehead tower of the orthogonal group (fivebrane 6-group $\to$ string 2-group $\to$ spin group $\to$ special orthogonal group $\to$ orthogonal group);

• in the middle, its restriction to deloopings of finite groups and their universal ∞-group extensions ($\cdots \to$ covering of alternating group $\to$ alternating group $\to$ symmetric group)

• on the left the homotopy fibers of each stage.

Notice that the squares on the right are not homotopy pullback squares. (The homotopy pullback of the string 2-group along $\tilde A \hookrightarrow Spin(n)$ is a $\mathbf{B}U(1)$-extension of $\tilde A$, but here we get the universal finite 2-group extension, by $\mathbb{Z}/24$ instead.

Cardinality of symmetric groups

Recall that two sets $A$ and $B$ have the same cardinality if $A$ is in bijection with $B$.

Given a natural number $n:\mathbb{N}$, the symmetric group on the finite set with $n$ elements $\Sigma(n)$ is in bijection with the finite set $\mathrm{Fin}(n!)$ elements, where $n!$ is the factorial of $n$.

The symmetric group on the natural numbers $\mathrm{Sym}(\mathbb{N})$ is an uncountable set in bijection with the endofunction set $\mathbb{N}^\mathbb{N}$. In the context of excluded middle, this is in bijection with $\mathcal{P}(\mathbb{N})$, the power set of the natural numbers.

Assuming the axiom of choice, given an infinite set $A$, there is a bijection $\mathrm{Sym}(A) \cong \mathcal{P}(A)$ between the symmetric group of $A$ and the power set of $A$.

Related concepts

• permutation, permutation representation, permutation matrix

• bijection set

• Cayley distance, Kendall distance

  Cayley distance kernel, Mallows kernel

• braid group

• alternating group

• symmetric groupoid

• signature of a permutation

• Young subgroup

• permutation D-brane

• automorphism group, automorphism infinity-group

• autoequivalence type

References

General

Textbook accounts:

• Bruce Sagan, The symmetric group, Springer 2001 (doi:10.1007/978-1-4757-6804-6, pdf)

Discussion of the classifying spaces of symmetric groups:

• Carl-Friedrich Bödigheimer, Stable splittings of mapping spaces, Algebraic topology. Springer 1987. 174-187 (pdf)

See also

• Wikipedia, Symmetric group

• Narthana Epa, Nora Ganter, Platonic and alternating 2-groups, Higher Structures 1(1):122-146, 2017 (arXiv:1605.09192)

• Michael Hopkins, Mark Mahowald, Hal Sadofsky, Constructions of elements in Picard groups, Contemporary mathematics, Volume 158, 1994 in Eric Friedlander, Mark Mahowald (eds.), Topology and Representation theory (doi:10.1090/conm/158/01454)

For the operadic structure of permutations:

• Benoit Fresse, Volume 1, Chapter 1 of: Homotopy of Operads and Grothendieck-Teichmüller Groups (Volumes 1 & 2), website

For more on permutation patterns, see:

• Wikipedia, Permutation pattern.

• Étienne Ghys, A Singular Mathematical Promenade, August 2017. arXiv:1612.06373 author pdf

That in the context of the axiom of choice, the symmetric group of an infinite set is in bijection (i.e. has the same cardinality) with the power set of that infinite set, see:

• John Dawson; Paul Howard, Factorials of infinite cardinals, Fundamenta Mathematicae (1976), Volume: 93, Issue: 3, page 185-195, ISSN: 0016-2736 (EuDML)